#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>

// Leetcode#4 寻找两个正序数组的中位数
// 中位数的函义: 如果两个数组加起来的长度是奇数 ， 就是中间的， ， 如果是偶数中位数就是   两个相加除2 

// 暴力解法.   时间复杂度  O(m+n) 空间复杂度 O(m + n)
namespace S1 {
class Solution {
public:
    double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
 	
	if (nums1.size() == 0 && nums2.size() == 0) {
		return 0; 
	}   
	
	int i = 0, j = 0;
	// 1. 合并两个有序的数组
	//
	std::vector<int> comp;
	int maxSize = nums1.size() + nums2.size();
	comp.reserve(maxSize);
	int n = nums1.size();
	int m = nums2.size();
	while(i < n && j < m) {
		if (nums1[i] < nums2[j]) {
			comp.push_back(nums1[i]);
			i++;
		} else {
			comp.push_back(nums2[j]);
			j++;
		}
	}
	// 剩余元素
	if (i < n) {
		for (; i<n;i++){
			comp.push_back(nums1[i]);
		}
	} else if ( j < m){
		for (; j < m; j++) {
			comp.push_back(nums2[j]);
		}
	}
	// 2. 找中余数
	if (maxSize % 2 == 1) {
		return comp[maxSize/2];	
	} else {
		int mid = maxSize/2;
		return (comp[mid-1] + comp[mid]) / 2.0;
	}
	   
    }
};
}

// 优化方法  二分查找
namespace S2 {
	class Solution {
		public:
		double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
			//1.比较长度短的数组 == 减少次数
			if (nums1.size() > nums2.size()) {
				return findMedianSortedArrays(nums2, nums1);
			} // 经过这里后 nums1的长度小于nums2的长度
			
			//划分 === 整个算法优化的重点
			int m = nums1.size();
			int n = nums2.size();
			int total = m + n;
			int half = (m + n + 1) / 2; //中位线 左半部分 - 包含前k小的元素  右半部分 - 包含剩余部分    (左半部分应有的元素数)

			int low = 0, high = m;
			double median = 0.0;
			while (low <= high) {
				// i: nums1的分割点（左半部分元素数）
				int i = low + (high - low)/2;
				// j: nums2的分割点（左半部分元素数 = 总数的一半 - i）
				int j = half - i;

				// 处理边界情况（当分割点在数组边界时）
				int nums1_left_max = (i > 0) ? nums1[i - 1] : INT_MIN;
				int nums1_right_min = (i < m) ? nums1[i] : INT_MAX;
				int nums2_left_max = (j > 0) ? nums2[j - 1] : INT_MIN;
				int nums2_right_min = (j < n) ? nums2[j] : INT_MAX;

				if (nums1_left_max <= nums2_right_min && nums2_left_max <= nums1_right_min) {
					if (total % 2 == 1) { // 奇数
						median = std::max(nums1_left_max, nums2_left_max);
					} else { // 偶数
						int left_max = std::max(nums1_left_max, nums2_left_max);
						int right_min = std::min(nums1_right_min, nums2_right_min);
						median = (left_max + right_min) / 2.0;
					}
					break;
				} else if (nums1_left_max > nums2_right_min) { // 通过这个判断来决定
					high = i - 1;   //  i太大，向左搜索
				} else {
					low = i + 1; //  i太小，向右搜索
				}
			}
			return median;
		}
	};
}

int main() {

	std::vector<int> num1 {1,3,8,9,15};
	std::vector<int> num2 { 7,11,18,19,21,25 };

	S2::Solution s;
	std::cout << s.findMedianSortedArrays(num1, num2) << std::endl;
	return 0;
}
